home *** CD-ROM | disk | FTP | other *** search
/ Disc to the Future 2 / Disc to the Future Part II Programmer's Reference (Wayzata Technology)(6013)(1992).bin / MAC / MPW_TOOL / TOOLS / TOOLS_WI / BYACC__ / LALR.C < prev    next >
C/C++ Source or Header  |  1989-11-19  |  10KB  |  653 lines
  1. #include <stdio.h>
  2. #include "defs.h"
  3. #include "dep.h"
  4. #include "gram.h"
  5. #include "new.h"
  6. #include "state.h"
  7.  
  8. typedef
  9.   struct shorts
  10.     {
  11.       struct shorts *next;
  12.       short value;
  13.     }
  14.   shorts;
  15.  
  16. int tokensetsize;
  17. short *lookaheads;
  18. short *LAruleno;
  19. unsigned *LA;
  20. short *accessing_symbol;
  21. core **state_table;
  22. shifts **shift_table;
  23. reductions **reduction_table;
  24. short *goto_map;
  25. short *from_state;
  26. short *to_state;
  27.  
  28. short **transpose();
  29.  
  30. static int infinity;
  31. static int maxrhs;
  32. static int ngotos;
  33. static unsigned *F;
  34. static short **includes;
  35. static shorts **lookback;
  36. static short **R;
  37. static short *INDEX;
  38. static short *VERTICES;
  39. static int top;
  40.  
  41.  
  42. lalr()
  43. {
  44.   tokensetsize = WORDSIZE(ntokens);
  45.  
  46.   set_state_table();
  47.   set_accessing_symbol();
  48.   set_shift_table();
  49.   set_reduction_table();
  50.   set_maxrhs();
  51.   initialize_LA();
  52.   set_goto_map();
  53.   initialize_F();
  54.   build_relations();
  55.   compute_FOLLOWS();
  56.   compute_lookaheads();
  57. }
  58.  
  59.  
  60.  
  61. set_state_table()
  62. {
  63.   register core *sp;
  64.  
  65.   state_table = NEW2(nstates, core *);
  66.  
  67.   for (sp = first_state; sp; sp = sp->next)
  68.     state_table[sp->number] = sp;
  69. }
  70.  
  71.  
  72.  
  73. set_accessing_symbol()
  74. {
  75.   register core *sp;
  76.  
  77.   accessing_symbol = NEW2(nstates, short);
  78.  
  79.   for (sp = first_state; sp; sp = sp->next)
  80.     accessing_symbol[sp->number] = sp->accessing_symbol;
  81. }
  82.  
  83.  
  84.  
  85. set_shift_table()
  86. {
  87.   register shifts *sp;
  88.  
  89.   shift_table = NEW2(nstates, shifts *);
  90.  
  91.   for (sp = first_shift; sp; sp = sp->next)
  92.     shift_table[sp->number] = sp;
  93. }
  94.  
  95.  
  96.  
  97. set_reduction_table()
  98. {
  99.   register reductions *rp;
  100.  
  101.   reduction_table = NEW2(nstates, reductions *);
  102.  
  103.   for (rp = first_reduction; rp; rp = rp->next)
  104.     reduction_table[rp->number] = rp;
  105. }
  106.  
  107.  
  108.  
  109. set_maxrhs()
  110. {
  111.   register short *itemp;
  112.   register short *item_end;
  113.   register int length;
  114.   register int max;
  115.  
  116.   length = 0;
  117.   max = 0;
  118.   item_end = ritem + nitems;
  119.   for (itemp = ritem; itemp < item_end; itemp++)
  120.     {
  121.       if (*itemp > 0)
  122.     {
  123.       length++;
  124.     }
  125.       else
  126.     {
  127.       if (length > max) max = length;
  128.       length = 0;
  129.     }
  130.     }
  131.  
  132.   maxrhs = max;
  133. }
  134.  
  135.  
  136.  
  137. initialize_LA()
  138. {
  139.   register int i, j, k;
  140.   register reductions *rp;
  141.  
  142.   lookaheads = NEW2(nstates + 1, short);
  143.  
  144.   k = 0;
  145.   for (i = 0; i < nstates; i++)
  146.     {
  147.       lookaheads[i] = k;
  148.       rp = reduction_table[i];
  149.       if (rp)
  150.     k += rp->nreds;
  151.     }
  152.   lookaheads[nstates] = k;
  153.  
  154.   LA = NEW2(k * tokensetsize, unsigned);
  155.   LAruleno = NEW2(k, short);
  156.   lookback = NEW2(k, shorts *);
  157.  
  158.   k = 0;
  159.   for (i = 0; i < nstates; i++)
  160.     {
  161.       rp = reduction_table[i];
  162.       if (rp)
  163.     {
  164.       for (j = 0; j < rp->nreds; j++)
  165.         {
  166.           LAruleno[k] = rp->rules[j];
  167.           k++;
  168.         }
  169.     }
  170.     }
  171. }
  172.  
  173.  
  174. set_goto_map()
  175. {
  176.   register shifts *sp;
  177.   register int i;
  178.   register int symbol;
  179.   register int k;
  180.   register short *temp_map;
  181.   register int state2;
  182.   register int state1;
  183.  
  184.   goto_map = NEW2(nvars + 1, short) - ntokens;
  185.   temp_map = NEW2(nvars + 1, short) - ntokens;
  186.  
  187.   ngotos = 0;
  188.   for (sp = first_shift; sp; sp = sp->next)
  189.     {
  190.       for (i = sp->nshifts - 1; i >= 0; i--)
  191.     {
  192.       symbol = accessing_symbol[sp->shifts[i]];
  193.  
  194.       if (ISTOKEN(symbol)) break;
  195.  
  196.       if (ngotos == MAXSHORT)
  197.         fatal("too many gotos");
  198.  
  199.       ngotos++;
  200.       goto_map[symbol]++;
  201.         }
  202.     }
  203.  
  204.   k = 0;
  205.   for (i = ntokens; i < nsyms; i++)
  206.     {
  207.       temp_map[i] = k;
  208.       k += goto_map[i];
  209.     }
  210.  
  211.   for (i = ntokens; i < nsyms; i++)
  212.     goto_map[i] = temp_map[i];
  213.  
  214.   goto_map[nsyms] = ngotos;
  215.   temp_map[nsyms] = ngotos;
  216.  
  217.   from_state = NEW2(ngotos, short);
  218.   to_state = NEW2(ngotos, short);
  219.  
  220.   for (sp = first_shift; sp; sp = sp->next)
  221.     {
  222.       state1 = sp->number;
  223.       for (i = sp->nshifts - 1; i >= 0; i--)
  224.     {
  225.       state2 = sp->shifts[i];
  226.       symbol = accessing_symbol[state2];
  227.  
  228.       if (ISTOKEN(symbol)) break;
  229.  
  230.       k = temp_map[symbol]++;
  231.       from_state[k] = state1;
  232.       to_state[k] = state2;
  233.     }
  234.     }
  235.  
  236.   FREE2(temp_map,ntokens);
  237. }
  238.  
  239.  
  240.  
  241. /*  Map_goto maps a state/symbol pair into its numeric representation.    */
  242.  
  243. int
  244. map_goto(state, symbol)
  245. int state;
  246. int symbol;
  247. {
  248.   register int high;
  249.   register int low;
  250.   register int middle;
  251.   register int s;
  252.  
  253.   low = goto_map[symbol];
  254.   high = goto_map[symbol + 1];
  255.  
  256.   while (low <= high)
  257.     {
  258.       middle = (low + high) / 2;
  259.       s = from_state[middle];
  260.       if (s == state)
  261.     return (middle);
  262.       else if (s < state)
  263.     low = middle + 1;
  264.       else
  265.     high = middle - 1;
  266.     }
  267.  
  268.   panic("map_goto");
  269.  
  270. /* NOTREACHED */
  271. }
  272.  
  273.  
  274.  
  275. initialize_F()
  276. {
  277.   register int i;
  278.   register int j;
  279.   register int k;
  280.   register shifts *sp;
  281.   register short *edge;
  282.   register unsigned *rowp;
  283.   register short *rp;
  284.   register short **reads;
  285.   register int nedges;
  286.   register int stateno;
  287.   register int symbol;
  288.   register int nwords;
  289.  
  290.   nwords = ngotos * tokensetsize;
  291.   F = NEW2(nwords, unsigned);
  292.  
  293.   reads = NEW2(ngotos, short *);
  294.   edge = NEW2(ngotos + 1, short);
  295.   nedges = 0;
  296.  
  297.   rowp = F;
  298.   for (i = 0; i < ngotos; i++)
  299.     {
  300.       stateno = to_state[i];
  301.       sp = shift_table[stateno];
  302.  
  303.       if (sp)
  304.     {
  305.       k = sp->nshifts;
  306.  
  307.       for (j = 0; j < k; j++)
  308.         {
  309.           symbol = accessing_symbol[sp->shifts[j]];
  310.           if (ISVAR(symbol))
  311.         break;
  312.           SETBIT(rowp, symbol);
  313.         }
  314.  
  315.       for (; j < k; j++)
  316.         {
  317.           symbol = accessing_symbol[sp->shifts[j]];
  318.           if (nullable[symbol])
  319.         edge[nedges++] = map_goto(stateno, symbol);
  320.         }
  321.     
  322.       if (nedges)
  323.         {
  324.           reads[i] = rp = NEW2(nedges + 1, short);
  325.  
  326.           for (j = 0; j < nedges; j++)
  327.         rp[j] = edge[j];
  328.  
  329.           rp[nedges] = -1;
  330.           nedges = 0;
  331.         }
  332.     }
  333.  
  334.       rowp += tokensetsize;
  335.     }
  336.  
  337.   SETBIT(F, 0);
  338.   digraph(reads);
  339.  
  340.   for (i = 0; i < ngotos; i++)
  341.     {
  342.       if (reads[i])
  343.     FREE(reads[i]);
  344.     }
  345.  
  346.   FREE(reads);
  347.   FREE(edge);
  348. }
  349.  
  350.  
  351.  
  352. build_relations()
  353. {
  354.   register int i;
  355.   register int j;
  356.   register int k;
  357.   register short *rulep;
  358.   register short *rp;
  359.   register shifts *sp;
  360.   register int length;
  361.   register int nedges;
  362.   register int done;
  363.   register int state1;
  364.   register int stateno;
  365.   register int symbol1;
  366.   register int symbol2;
  367.   register short *shortp;
  368.   register short *edge;
  369.   register short *states;
  370.   register short **new_includes;
  371.  
  372.   includes = NEW2(ngotos, short *);
  373.   edge = NEW2(ngotos + 1, short);
  374.   states = NEW2(maxrhs + 1, short);
  375.  
  376.   for (i = 0; i < ngotos; i++)
  377.     {
  378.       nedges = 0;
  379.       state1 = from_state[i];
  380.       symbol1 = accessing_symbol[to_state[i]];
  381.  
  382.       for (rulep = derives[symbol1]; *rulep >= 0; rulep++)
  383.     {
  384.       length = 1;
  385.       states[0] = state1;
  386.       stateno = state1;
  387.  
  388.       for (rp = ritem + rrhs[*rulep]; *rp > 0; rp++)
  389.         {
  390.           symbol2 = *rp;
  391.           sp = shift_table[stateno];
  392.           k = sp->nshifts;
  393.  
  394.           for (j = 0; j < k; j++)
  395.         {
  396.           stateno = sp->shifts[j];
  397.           if (accessing_symbol[stateno] == symbol2) break;
  398.         }
  399.  
  400.           states[length++] = stateno;
  401.         }
  402.  
  403.       add_lookback_edge(stateno, *rulep, i);
  404.  
  405.       length--;
  406.       done = 0;
  407.       while (!done)
  408.         {
  409.           done = 1;
  410.           rp--;
  411.           if (ISVAR(*rp))
  412.         {
  413.           stateno = states[--length];
  414.           edge[nedges++] = map_goto(stateno, *rp);
  415.           if (nullable[*rp] && length > 0) done = 0;
  416.         }
  417.         }
  418.     }
  419.  
  420.       if (nedges)
  421.     {
  422.       includes[i] = shortp = NEW2(nedges + 1, short);
  423.       for (j = 0; j < nedges; j++)
  424.         shortp[j] = edge[j];
  425.       shortp[nedges] = -1;
  426.     }
  427.     }
  428.  
  429.   new_includes = transpose(includes, ngotos);
  430.  
  431.   for (i = 0; i < ngotos; i++)
  432.     FREE(includes[i]);
  433.  
  434.   FREE(includes);
  435.  
  436.   includes = new_includes;
  437.  
  438.   FREE(edge);
  439.   FREE(states);
  440. }
  441.  
  442.  
  443.  
  444. add_lookback_edge(stateno, ruleno, gotono)
  445. int stateno, ruleno, gotono;
  446. {
  447.   register int i, k;
  448.   register int found;
  449.   register shorts *sp;
  450.  
  451.   i = lookaheads[stateno];
  452.   k = lookaheads[stateno + 1];
  453.   found = 0;
  454.   while (!found && i < k)
  455.     {
  456.       if (LAruleno[i] == ruleno)
  457.     found = 1;
  458.       else
  459.     i++;
  460.     }
  461.  
  462.   if (found == 0)
  463.     panic("add_lookback_edge");
  464.  
  465.   sp = NEW(shorts);
  466.   sp->next = lookback[i];
  467.   sp->value = gotono;
  468.   lookback[i] = sp;
  469. }
  470.  
  471.  
  472.  
  473. short **
  474. transpose(R, n)
  475. short **R;
  476. int n;
  477. {
  478.   register short **new_R;
  479.   register short **temp_R;
  480.   register short *nedges;
  481.   register short *sp;
  482.   register int i;
  483.   register int k;
  484.  
  485.   nedges = NEW2(n, short);
  486.  
  487.   for (i = 0; i < n; i++)
  488.     {
  489.       sp = R[i];
  490.       if (sp)
  491.     {
  492.       while (*sp >= 0)
  493.         nedges[*sp++]++;
  494.     }
  495.     }
  496.  
  497.   new_R = NEW2(n, short *);
  498.   temp_R = NEW2(n, short *);
  499.  
  500.   for (i = 0; i < n; i++)
  501.     {
  502.       k = nedges[i];
  503.       if (k > 0)
  504.     {
  505.       sp = NEW2(k + 1, short);
  506.       new_R[i] = sp;
  507.       temp_R[i] = sp;
  508.       sp[k] = -1;
  509.     }
  510.     }
  511.  
  512.   FREE(nedges);
  513.  
  514.   for (i = 0; i < n; i++)
  515.     {
  516.       sp = R[i];
  517.       if (sp)
  518.     {
  519.       while (*sp >= 0)
  520.         *temp_R[*sp++]++ = i;
  521.     }
  522.     }
  523.  
  524.   FREE(temp_R);
  525.  
  526.   return (new_R);
  527. }
  528.  
  529.  
  530.  
  531. compute_FOLLOWS()
  532. {
  533.   digraph(includes);
  534. }
  535.  
  536.  
  537. compute_lookaheads()
  538. {
  539.   register int i, n;
  540.   register unsigned *fp1, *fp2, *fp3;
  541.   register shorts *sp,*sp2;
  542.   register unsigned *rowp;
  543.  
  544.   rowp = LA;
  545.   n = lookaheads[nstates];
  546.   for (i = 0; i < n; i++)
  547.     {
  548.       fp3 = rowp + tokensetsize;
  549.       for (sp = lookback[i]; sp; sp = sp->next)
  550.     {
  551.       fp1 = rowp;
  552.       fp2 = F + tokensetsize * sp->value;
  553.       while (fp1 < fp3)
  554.         *fp1++ |= *fp2++;
  555.     }
  556.       rowp = fp3;
  557.     }
  558.  
  559.   for (i = 0; i < n; i++)
  560.     for (sp = lookback[i]; sp; ){
  561.         sp2 = sp;
  562.         sp = sp->next;
  563.         FREE(sp2);
  564.     }
  565.  
  566.   FREE(lookback);
  567.   FREE(F);
  568. }
  569.  
  570.  
  571. digraph(relation)
  572. short **relation;
  573. {
  574.   register int i;
  575.  
  576.   infinity = ngotos + 2;
  577.   INDEX = NEW2(ngotos + 1, short);
  578.   VERTICES = NEW2(ngotos + 1, short);
  579.   top = 0;
  580.  
  581.   R = relation;
  582.  
  583.   for (i = 0; i < ngotos; i++)
  584.     INDEX[i] = 0;
  585.  
  586.   for (i = 0; i < ngotos; i++)
  587.     {
  588.       if (INDEX[i] == 0 && R[i])
  589.     traverse(i);
  590.     }
  591.  
  592.   FREE(INDEX);
  593.   FREE(VERTICES);
  594. }
  595.  
  596.  
  597.  
  598. traverse(i)
  599. register int i;
  600. {
  601.   register unsigned *fp1;
  602.   register unsigned *fp2;
  603.   register unsigned *fp3;
  604.   register int j;
  605.   register short *rp;
  606.  
  607.   int height;
  608.   unsigned *base;
  609.  
  610.   VERTICES[++top] = i;
  611.   INDEX[i] = height = top;
  612.  
  613.   base = F + i * tokensetsize;
  614.   fp3 = base + tokensetsize;
  615.  
  616.   rp = R[i];
  617.   if (rp)
  618.     {
  619.       while ((j = *rp++) >= 0)
  620.     {
  621.       if (INDEX[j] == 0)
  622.         traverse(j);
  623.  
  624.       if (INDEX[i] > INDEX[j])
  625.         INDEX[i] = INDEX[j];
  626.  
  627.       fp1 = base;
  628.       fp2 = F + j * tokensetsize;
  629.  
  630.       while (fp1 < fp3)
  631.         *fp1++ |= *fp2++;
  632.     }
  633.     }
  634.  
  635.   if (INDEX[i] == height)
  636.     {
  637.       for (;;)
  638.     {
  639.       j = VERTICES[top--];
  640.       INDEX[j] = infinity;
  641.  
  642.       if (i == j)
  643.         break;
  644.  
  645.       fp1 = base;
  646.       fp2 = F + j * tokensetsize;
  647.  
  648.       while (fp1 < fp3)
  649.         *fp2++ = *fp1++;
  650.     }
  651.     }
  652. }
  653.